package binary_tree.LeetCode;

public class Num236 {
   TreeNode lcb;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root==null){
           return null;
       }
       find(root,p,q);
       return lcb;
    }

    private boolean find(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        //先找左树中是否有p，q
        int left=find(root.left,p,q)?1:0;
        //找右树中是否有p,q
        int right=find(root.right,p,q)?1:0;
        //看此时的root是否要查找的p,q
        int mid=(root==p||root==q)?1:0;
        //在左右中加起来为2时说明此时就是最近公共祖先。
        if(left+right+mid==2){
            lcb=root;
            return true;
        }
        return left+right+mid>0;
    }

}
